package com.captain.leetcode.回溯算法;

import java.util.ArrayList;
import java.util.List;

/**
 * @author captain
 * @Des
 * @Date 2021/7/19 22:23
 */
public class 八皇后问题回溯 {

    /**
     * 索引 = 行
     * 值 = 列
     */
    private int[] cols;

    /**
     * 结果集
     */
    private final List<List<String>> result = new ArrayList<>();

    //N皇后问题
    public List<List<String>> solveNQueens(int n) {
        if (n < 1) return new ArrayList<>();
        cols = new int[n];
        //从0行开始
        place(0);
        return result;
    }

    /**
     * 回溯寻找路径
     *
     * @param row
     */
    private void place(int row) {
        //如果满足条件
        if (row == cols.length) {
            show();
            //结束
            return;
        }

        //每一行都有八种走法
        for (int col = 0; col < cols.length; col++) {
            //判断当前格子是否能放皇后,能就跳到下一行
            if (isValid(row, col)) {
                //某一行某一列 放皇后,然后继续下一行
                cols[row] = col;
                //递归下一行
                place(row + 1);
            }
        }
        //不满足时,直接回溯到上一层进行循环

    }

    /**
     * 检测该格子是否能摆放皇后
     *
     * @param row
     * @param col
     * @return
     */
    private boolean isValid(int row, int col) {
        //判断之前已经完成的行数
        for (int i = 0; i < row; i++) {
            //当前列已经存在值
            if (cols[i] == col) {
                return false;
            }

            //判断斜角是否存在值
            if ((row - i) == Math.abs(col - cols[i])) {
                return false;
            }
        }
        return true;
    }

    void show() {
        List<String> list = new ArrayList<>();
        for (int i : cols) {
            StringBuilder builder = new StringBuilder();
            for (int col = 0; col < cols.length; col++) {
                if (i == col) {
                    builder.append("Q");
                } else {
                    builder.append(".");
                }
            }
            list.add(builder.toString());
        }
        result.add(list);
    }
}
